﻿#pragma once
#include <assert.h>
#include <iostream>
using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	pair<K, V> _kv;//k:v结构
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _perent;
	int _bf;//平衡因子

	AVLTreeNode(const pair<K, V>& kv)//构造
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _perent(nullptr)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;//重命名
public:
	//插入
	bool Insert(const pair<K, V>& kv)
	{
		//树为空
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		//树不为空
		Node* cur = _root;
		Node* perent = nullptr;
		while (cur)
		{
			if (kv.first > cur->_kv.first)
			{
				perent = cur;
				cur = cur->_right;
			}
			else if (kv.first < cur->_kv.first)
			{
				perent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		//插入
		cur = new Node(kv);
		if (kv.first > perent->_kv.first)
		{
			perent->_right = cur;
		}
		else
		{
			perent->_left = cur;
		}
		cur->_perent = perent;

		//更新平衡因子
		//...


		return true;
	}

private:
	Node* _root = nullptr;//根节点
};
